import unittest
from alg import Solution
from gen import generate_random_tree, deserialize, serialize

class TestLevelOrder(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_empty_tree(self):
        root = None
        self.assertEqual(self.solution.levelOrder(root), [])

    def test_single_node(self):
        root = deserialize([1])
        self.assertEqual(self.solution.levelOrder(root), [[1]])

    def test_example(self):
        root = deserialize([3,9,20,None,None,15,7])
        self.assertEqual(self.solution.levelOrder(root), [[3], [9, 20], [15, 7]])

    def test_left_skewed(self):
        root = deserialize([1,2,None,3,None,4])
        self.assertEqual(self.solution.levelOrder(root), [[1], [2], [3], [4]])

    def test_right_skewed(self):
        root = deserialize([1,None,2,None,3,None,4])
        self.assertEqual(self.solution.levelOrder(root), [[1], [2], [3], [4]])

    def test_random_generated(self):
        for _ in range(100):  # 生成100个随机测试用例
            n = random.randint(1, 100)
            root = generate_random_tree(n)
            
            # 使用BFS方法计算预期结果
            expected = []
            if root:
                queue = [root]
                while queue:
                    level = []
                    next_level = []
                    for node in queue:
                        level.append(node.val)
                        if node.left:
                            next_level.append(node.left)
                        if node.right:
                            next_level.append(node.right)
                    expected.append(level)
                    queue = next_level
            
            # 比较结果
            actual = self.solution.levelOrder(root)
            self.assertEqual(actual, expected)

if __name__ == '__main__':
    unittest.main()